#include <iostream.h>
#include <stdio.h>
#include <conio.h>
#include <iomanip.h>
#include <stdlib.h>

int nechet[100];
int count_n = 0;

struct tree
{
  int a;
  tree* pleft;
  tree* pright;
};

tree *parent = NULL;
tree *root = NULL;

void build(tree *tt, int n);
tree* find(int x, tree *pt);
void delete_elem(int x);
void print_tree(tree* ptr, int h);
tree* delete_tree(tree* t);

void main()
{
  randomize();
  clrscr();
  int n = 0;
  cout <<"How many elements do you want to make? ";
  cin >>n;
  root = new tree;
  root->a = random(100);
  root->pleft = NULL;
  root->pright = NULL;
  for (int i=0; i<n; i++)
  {
    build(root, random(100));
  }

  print_tree(root, 1);
  cout<< endl<<endl;
  for (int j=0; j<count_n; j++)
  {
    delete_elem(nechet[j]);
  }
  print_tree(root, 1);
  root = delete_tree(root);
  getch();
}


void build(tree *tt, int n)
{
  if (n < tt->a)
  {
    if(tt->pleft == NULL)
    {
      tree *left = new tree;
      tt->pleft = left;
      left->a = n;
      left->pleft = NULL;
      left->pright = NULL;
    }
    else
    {
      build(tt->pleft, n);
    }
  }
  else
  {
    if (tt->pright == NULL)
    {
      tree *right = new tree;
      tt->pright = right;
      right->a = n;
      right->pleft = NULL;
      right->pright = NULL;
    }
    else
    {
      build(tt->pright, n);
    }
  }
}

int z=0;
void print_tree(tree* ptr, int h)
{

  if (ptr != NULL)
  {
    print_tree(ptr->pright, h + 1);
    for (int i=1; i<=h; i++)
    {
      cout<< "   ";
    }
    cout<< ptr->a<< endl;
    if((ptr->a % 2) == 1)
    {
      nechet[z++] = ptr->a;
      count_n = z;
    }
    print_tree(ptr->pleft, h+1);
  }
}


tree* find(int x, tree *pt)
{
  while (pt != NULL)
  {
    if (x == pt->a)
    {
      break;
    }
    else
    {
      parent = pt;
      if (x < pt->a)
      {
        pt = pt->pleft;
      }
      else
      {
        pt = pt->pright;
      }
    }
  }
  return pt;
}


void delete_elem(int x)
{
  tree *dn = NULL;
  tree *rn = NULL;
  if ((dn=find(x, root)) == NULL)
  {
    return;
  }
  if (dn->pright == NULL)
  {
    rn = dn->pleft;
  }
  else if (dn->pleft == NULL)
  {
    rn = dn->pright;
  }
  else
  {
    tree *prn = dn;
    rn = dn->pleft;
    while (rn->pright != NULL)
    {
      prn = rn;
      rn = rn->pright;
    }
    if (prn == dn)
    {
      rn->pright = dn->pright;
    }
    else
    {
      prn->pright = rn->pleft;
      rn->pleft = dn->pleft;
      rn->pright = dn->pright;
    }
  }
  if (parent == NULL)
  {
    root = rn;
  }
  else
  {
    if (dn->a < parent->a)
    {
      parent->pleft = rn;
    }
    else
    {
      parent->pright = rn;
    }
  }
  delete(dn);
}


tree *delete_tree(tree* t)
{
  if (t != NULL)
  {
    delete_tree(t->pleft);
    delete_tree(t->pright);
    delete t;
  }
  return NULL;
}

